#ifndef COMMON_H
#define COMMON_H

#include <iostream>
#include <iomanip>
#include <array>
#include <vector>
#include <cassert>
#include <algorithm>
#include <iterator>
#include <numeric>	// for iota
#include <chrono>
#include <windows.h>

using namespace std;

namespace CodeMood {

const int M = 1000000;

#define TIME0(X) { \
	LARGE_INTEGER start, stop, freq; \
	QueryPerformanceCounter(&start); \
	{X;} \
	QueryPerformanceCounter(&stop); \
	QueryPerformanceFrequency(&freq); \
	double duration = (double)(stop.QuadPart - start.QuadPart) / (double)(freq.QuadPart); \
	cout << setw(10) << fixed << duration << " " << #X << endl; \
}

#define TIME(X) { \
	auto t0 = chrono::high_resolution_clock::now(); \
	{X;} \
	auto t1 = chrono::high_resolution_clock::now(); \
	cout << setw(10) << fixed << (double)chrono::duration_cast<chrono::nanoseconds>(t1-t0).count() / (double)1000000000 << " " << #X << endl; \
}
void print(const vector<int>& vec)
{
	for (int i = 0; i < M; i++)
		cout << vec[i] << " ";
	cout << endl;
}

typedef void (*sorting_algorithm)(vector<int>& vec);

void test_sorting(sorting_algorithm algo, vector<int>& vec)
{
	//cout << "sort start" << endl;
	algo(vec);
	//cout << "sort end" << endl;
	//assert(is_sorted(begin(arr), end(arr)));
}

struct GenIota {
	GenIota(int i = 0) : i_(i)
	{}
	int operator()() 
	{
		return i_++;
	}
	int i_;
};

template<class Iter>
void generate_random(Iter begin, Iter end)
{
	// 3 ways to generate 0...M
	/*for (int i = 0; i < M; ++i) {
		arr[i] = i;
	}*/
	iota(begin, end, 0);
	//generate(begin(arr), end(arr), GenIota());
	srand(0);
	random_shuffle(begin, end);
}

void shuffle(vector<int>& vec, int seed = 0)
{
	srand(seed);
	random_shuffle(begin(vec), end(vec));
}

template<class Iter>
void shuffle(Iter begin, Iter end, int seed = 0)
{
	srand(seed);
	random_shuffle(begin, end);
}

}	//!namespace CodeMood

#endif	//!COMMON_H